7405. Ice Cream

Stepan and his friends went on holiday to Uzhlyandiya. While hiding from the heat, they decided to buy an ice cream. There exist n flavors of ice cream, numbered from 1 to n. Some tastes are incompatible, such couples should be avoided, otherwise it will be very unpleasant taste. Stepan wants to know the number of ways to choose three different flavors of ice cream so that among them there was no incompatible pair. The order of flavors in triples does not matter.

Input. The first line contains two nonnegative integers n and m (1 ≤ n ≤ 200, 1 ≤ m ≤ 10000) – the number of flavors and number of inconsistent pairs of flavors. Next m lines describe the pairs of incompatible flavors.

Output. Print one number – the number of ways to make a choice.

Sample input	Sample output
5 3 1 2 3 4 1 3	3

SOLUTION

loop

Algorithm analysis

Store in the two-dimensional array mas the pairs of incompatible tastes: assign mas[i][j] = 1 if tastes i and j are incompatible and mas[i][j] = 0 otherwise.

Find the number of triplets of different tastes in the problem. Using the triple loop iterate through the triples of tastes (i, j, k), where i < j < k. For each pair from the triple (i, j), (i, k), (j, k), check whether it is compatible.

Example

For the given example the possible triplets are (1 4 5), (2 3 5) and (2 4 5). The compatibility matrix of tastes has the form:

Algorithm realization

Declare an array mas to store the incompatible pairs.

#define MAX 201

int mas[MAX][MAX];

Read the input data.

scanf("%d %d", &n, &m);

memset(mas, 0, sizeof(mas));

Read the incompatible pairs, store information about them in the array mas.

for (i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

mas[a][b] = mas[b][a] = 1;

}

Iterate through the triples of tastes (i, j, k) so that i < j < k. For each pair from triple check is it compatible. Count the number of triples in the variable res.

res = 0;

for (i = 1; i <= n; i++)

for (j = i + 1; j <= n; j++)

for (k = j + 1; k <= n; k++)

if ((mas[i][j] == 0) && (mas[i][k] == 0) && (mas[j][k] == 0)) res++;

Print the number of ways to make a choice.

printf("%d\n", res);